#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=338 lang=cpp
 *
 * [338] 比特位计数
 */

// @lc code=start
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 0;
        if (n < 1) return dp;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (i % 2) dp[i] = dp[(i - 1) / 2] + 1;
            else dp[i] = dp[i / 2];
        }
        return dp;
    }
};
// @lc code=end

